package main

import (
	"fmt"
)

func main() {
	k, n := 3, 7
	fmt.Println(combinationSum3(k, n))
}

func combinationSum3(k int, n int) (ans [][]int) {
	comb := []int{}
	var dfs func(residue int, begin int)
	dfs = func(residue int, begin int) {
		if residue == 0 && len(comb) == k {
			ans = append(ans, append([]int(nil), comb...))
		}

		for i := begin; i < 10; i++ {
			if residue < i {
				break
			}

			comb = append(comb, i)
			dfs(residue-i, i+1)
			comb = comb[:len(comb)-1]
		}

	}

	dfs(n, 1)
	return

}
